#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*
* 代码实现逻辑：
* 题目要求的
* nums.length 在1到50,000区间范围内。
* nums[i] 是一个在0到49,999范围内的整数。
*/

int findShortestSubArray(int* nums, int numsSize){
    int Count[50000] = {0};
    int firstIdx[50000] = {0};
    int lastIdx[50000] = {0};
    int validDataArr[50000] = {0};
    int validDataCnt = 0;
    int idx;
    int degree = 0; // 数组的度
    int tmp;
    int result = numsSize; // 默认设置为最大的数组长度

    for (idx = 0 ; idx < numsSize; idx++){
        //判断数据是不是第一次出现
        if (Count[nums[idx]] == 0) { 
            // 第一次更新头尾位置
            firstIdx[nums[idx]] = idx;
            lastIdx[nums[idx]] = idx;
            validDataArr[validDataCnt] = nums[idx];
            validDataCnt++;
        } else {
            lastIdx[nums[idx]] = idx;
        }
        Count[nums[idx]]++;
        // 同步更新数组的度
        if (Count[nums[idx]] > degree) {
            degree = Count[nums[idx]];
        }
    }
    // 选出相同度的最小的子串
    // 优化下，不需要全部遍历50000，记录真实有效数值
    for(idx = 0 ; idx < validDataCnt; idx++) {
        // 在保持度条件下寻找最小长度的子串
        if (Count[validDataArr[idx]] == degree) {
            tmp = lastIdx[validDataArr[idx]]-firstIdx[validDataArr[idx]] + 1;
            if (tmp < result) {
                result =tmp;
            }
        }
    }

    return result;
}

